/ MacHack 1998 / MacHack 1998.toast / Programming Contest / MacHack Contest.sit / MacHack Contest / Problems Folder / Problem 08 - Packing / Solution.cp

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 00 0b 53 6f 6c 75 74 69 | 6f 6e 2e 63 70 00 00 00 |..Soluti|on.cp...|
|00000010| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000020| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000040| 00 54 45 58 54 43 57 49 | 45 00 00 00 00 00 00 00 |.TEXTCWI|E.......|
|00000050| 00 00 00 00 00 04 ee 00 | 00 01 9a b1 ae f6 56 b1 |........|......V.|
|00000060| ae f6 56 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |..V.....|........|
|00000070| 00 00 00 00 00 00 00 00 | 00 00 81 81 f5 af 00 00 |........|........|
|00000080| 2f 2a 0d 50 72 6f 62 6c | 65 6d 20 30 38 20 2d 20 |/*.Probl|em 08 - |
|00000090| 50 61 63 6b 69 6e 67 0d | 0d 50 6f 69 6e 74 41 72 |Packing.|.PointAr|
|000000a0| 72 61 79 20 3d 20 61 72 | 72 61 79 5b 30 2e 2e 30 |ray = ar|ray[0..0|
|000000b0| 5d 20 6f 66 20 50 6f 69 | 6e 74 3b 0d 50 6f 69 6e |] of Poi|nt;.Poin|
|000000c0| 74 41 72 72 61 79 50 74 | 72 20 3d 20 5e 50 6f 69 |tArrayPt|r = ^Poi|
|000000d0| 6e 74 41 72 72 61 79 3b | 0d 0d 70 72 6f 63 65 64 |ntArray;|..proced|
|000000e0| 75 72 65 20 50 61 63 6b | 42 6f 78 65 73 28 20 66 |ure Pack|Boxes( f|
|000000f0| 72 61 6d 65 3a 20 52 65 | 63 74 3b 20 62 6f 78 5f |rame: Re|ct; box_|
|00000100| 63 6f 75 6e 74 3a 20 55 | 49 6e 74 33 32 3b 20 62 |count: U|Int32; b|
|00000110| 6f 78 65 73 3a 20 50 6f | 69 6e 74 41 72 72 61 79 |oxes: Po|intArray|
|00000120| 3b 0d 74 6f 70 6c 65 66 | 74 73 3a 20 50 6f 69 6e |;.toplef|ts: Poin|
|00000130| 74 41 72 72 61 79 50 74 | 72 20 29 3b 0d 0d 59 6f |tArrayPt|r );..Yo|
|00000140| 75 72 20 74 61 73 6b 20 | 69 73 20 74 6f 20 70 61 |ur task |is to pa|
|00000150| 63 6b 20 61 20 73 65 74 | 20 6f 66 20 32 2d 64 69 |ck a set| of 2-di|
|00000160| 6d 65 6e 73 69 6f 6e 61 | 6c 20 62 6f 78 65 73 20 |mensiona|l boxes |
|00000170| 69 6e 74 6f 20 61 20 67 | 69 76 65 6e 20 66 72 61 |into a g|iven fra|
|00000180| 6d 65 20 72 65 63 74 61 | 6e 67 6c 65 0d 73 75 63 |me recta|ngle.suc|
|00000190| 68 20 74 68 61 74 20 74 | 68 65 20 69 6e 74 65 72 |h that t|he inter|
|000001a0| 69 6f 72 20 6f 66 20 74 | 68 65 20 62 6f 78 65 73 |ior of t|he boxes|
|000001b0| 20 64 6f 20 6e 6f 74 20 | 69 6e 74 65 72 73 65 63 | do not |intersec|
|000001c0| 74 2e 0d 0d 54 68 65 20 | 62 6f 78 20 64 69 6d 65 |t...The |box dime|
|000001d0| 6e 73 69 6f 6e 73 20 61 | 72 65 20 72 65 70 72 65 |nsions a|re repre|
|000001e0| 73 65 6e 74 65 64 20 62 | 79 20 68 65 69 67 68 74 |sented b|y height|
|000001f0| 20 28 74 68 65 20 2e 76 | 20 63 6f 6d 70 6f 6e 65 | (the .v| compone|
|00000200| 6e 74 29 20 61 6e 64 20 | 77 69 64 74 68 20 28 74 |nt) and |width (t|
|00000210| 68 65 0d 2e 68 20 63 6f | 6d 70 6f 6e 65 6e 74 29 |he..h co|mponent)|
|00000220| 20 69 6e 20 74 68 65 20 | 62 6f 78 65 73 20 61 72 | in the |boxes ar|
|00000230| 72 61 79 2e 20 20 59 6f | 75 20 6d 75 73 74 20 66 |ray.  Yo|u must f|
|00000240| 69 6e 64 20 61 20 77 61 | 79 20 74 6f 20 66 69 74 |ind a wa|y to fit|
|00000250| 20 61 6c 6c 20 74 68 65 | 0d 72 65 63 74 61 6e 67 | all the|.rectang|
|00000260| 6c 65 73 20 69 6e 73 69 | 64 65 20 74 68 65 20 66 |les insi|de the f|
|00000270| 72 61 6d 65 20 77 69 74 | 68 6f 75 74 20 6f 76 65 |rame wit|hout ove|
|00000280| 72 6c 61 70 70 69 6e 67 | 2e 20 20 4a 75 73 74 20 |rlapping|.  Just |
|00000290| 6c 69 6b 65 20 51 75 69 | 63 6b 44 72 61 77 20 73 |like Qui|ckDraw s|
|000002a0| 74 61 6e 64 61 72 64 0d | 72 65 63 74 61 6e 67 6c |tandard.|rectangl|
|000002b0| 65 73 2c 20 74 77 6f 20 | 61 64 6a 61 63 65 6e 74 |es, two |adjacent|
|000002c0| 20 72 65 63 74 61 6e 67 | 6c 65 73 20 63 6f 75 6c | rectang|les coul|
|000002d0| 64 20 68 61 76 65 20 74 | 68 65 20 73 61 6d 65 20 |d have t|he same |
|000002e0| 72 69 67 68 74 2f 6c 65 | 66 74 20 63 6f 6f 72 64 |right/le|ft coord|
|000002f0| 69 6e 61 74 65 2c 0d 73 | 6f 20 74 68 61 74 20 74 |inate,.s|o that t|
|00000300| 68 65 79 20 61 72 65 20 | 74 6f 75 63 68 69 6e 67 |hey are |touching|
|00000310| 20 62 75 74 20 6e 6f 74 | 20 6f 76 65 72 6c 61 70 | but not| overlap|
|00000320| 70 69 6e 67 2e 20 20 53 | 69 6d 69 6c 61 72 6c 79 |ping.  S|imilarly|
|00000330| 2c 20 72 65 63 74 61 6e | 67 6c 65 73 20 6d 61 79 |, rectan|gles may|
|00000340| 20 74 6f 75 63 68 0d 74 | 68 65 20 65 64 67 65 20 | touch.t|he edge |
|00000350| 6f 66 20 74 68 65 20 66 | 72 61 6d 65 2e 20 20 57 |of the f|rame.  W|
|00000360| 68 65 6e 20 79 6f 75 20 | 66 69 6e 64 20 61 20 73 |hen you |find a s|
|00000370| 6f 6c 75 74 69 6f 6e 2c | 20 79 6f 75 20 73 68 6f |olution,| you sho|
|00000380| 75 6c 64 20 72 65 74 75 | 72 6e 20 74 68 65 20 74 |uld retu|rn the t|
|00000390| 6f 70 6c 65 66 74 0d 63 | 6f 6f 72 64 69 6e 61 74 |opleft.c|oordinat|
|000003a0| 65 73 20 6f 66 20 65 61 | 63 68 20 72 65 63 74 61 |es of ea|ch recta|
|000003b0| 6e 67 65 2e 20 20 52 65 | 63 74 61 6e 67 6c 65 73 |nge.  Re|ctangles|
|000003c0| 20 6d 61 79 20 6f 6e 6c | 79 20 62 65 20 6d 6f 76 | may onl|y be mov|
|000003d0| 65 64 20 68 6f 72 72 69 | 7a 6f 6e 74 61 6c 6c 79 |ed horri|zontally|
|000003e0| 20 6f 72 0d 76 65 72 74 | 69 63 61 6c 6c 79 2c 20 | or.vert|ically, |
|000003f0| 74 68 65 79 20 6d 61 79 | 20 6e 6f 74 20 62 65 20 |they may| not be |
|00000400| 72 6f 74 61 74 65 64 2e | 0d 0d 45 78 61 6d 70 6c |rotated.|..Exampl|
|00000410| 65 0d 0d 66 72 61 6d 65 | 20 3d 20 28 31 30 2c 20 |e..frame| = (10, |
|00000420| 31 30 2c 20 31 30 30 2c | 20 31 30 30 20 29 0d 62 |10, 100,| 100 ).b|
|00000430| 6f 78 5f 63 6f 75 6e 74 | 20 3d 20 33 0d 62 6f 78 |ox_count| = 3.box|
|00000440| 65 73 20 3d 20 7b 20 28 | 35 30 2c 20 39 30 29 2c |es = { (|50, 90),|
|00000450| 20 28 34 30 2c 20 34 30 | 29 2c 20 28 34 30 2c 20 | (40, 40|), (40, |
|00000460| 35 30 29 20 7d 0d 0d 72 | 65 74 75 72 6e 0d 0d 74 |50) }..r|eturn..t|
|00000470| 6f 70 6c 65 66 74 73 20 | 3d 20 7b 20 28 31 30 2c |oplefts |= { (10,|
|00000480| 20 31 30 29 2c 20 28 36 | 30 2c 20 31 30 29 2c 20 | 10), (6|0, 10), |
|00000490| 28 36 30 2c 20 35 30 29 | 20 7d 0d 2a 2f 0d 0d 23 |(60, 50)| }.*/..#|
|000004a0| 69 6e 63 6c 75 64 65 20 | 22 53 6f 6c 75 74 69 6f |include |"Solutio|
|000004b0| 6e 2e 68 22 0d 0d 2f 2f | 20 46 69 6c 6c 20 69 6e |n.h"..//| Fill in|
|000004c0| 20 79 6f 75 72 20 73 6f | 6c 75 74 69 6f 6e 20 61 | your so|lution a|
|000004d0| 6e 64 20 74 68 65 6e 20 | 73 75 62 6d 69 74 20 74 |nd then |submit t|
|000004e0| 68 69 73 20 66 6f 6c 64 | 65 72 0d 0d 2f 2f 20 54 |his fold|er..// T|
|000004f0| 65 61 6d 20 4e 61 6d 65 | 3a 20 46 49 4c 4c 20 49 |eam Name|: FILL I|
|00000500| 4e 20 59 4f 55 52 20 54 | 45 41 4d 20 4e 41 4d 45 |N YOUR T|EAM NAME|
|00000510| 21 0d 0d 70 61 73 63 61 | 6c 20 76 6f 69 64 20 50 |!..pasca|l void P|
|00000520| 61 63 6b 42 6f 78 65 73 | 28 52 65 63 74 20 2a 66 |ackBoxes|(Rect *f|
|00000530| 72 61 6d 65 2c 20 55 49 | 6e 74 33 32 20 62 6f 78 |rame, UI|nt32 box|
|00000540| 5f 63 6f 75 6e 74 2c 20 | 50 6f 69 6e 74 20 62 6f |_count, |Point bo|
|00000550| 78 65 73 5b 5d 2c 20 50 | 6f 69 6e 74 20 74 6f 70 |xes[], P|oint top|
|00000560| 6c 65 66 74 73 5b 5d 20 | 29 0d 7b 0d 7d 0d 00 00 |lefts[] |).{.}...|
|00000570| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000580| 00 00 01 00 00 00 01 54 | 00 00 00 54 00 00 00 46 |.......T|...T...F|
|00000590| 2b 30 38 30 30 31 35 3a | 35 35 3a 33 32 20 31 39 |+080015:|55:32 19|
|000005a0| 39 38 00 00 00 00 00 00 | 00 00 b1 78 6a 77 00 00 |98......|...xjw..|
|000005b0| 0b 53 6f 6c 75 74 69 6f | 6e 2e 63 70 61 63 48 61 |.Solutio|n.cpacHa|
|000005c0| 63 6b 20 43 6f 6e 74 65 | 73 74 31 2e 73 69 74 69 |ck Conte|st1.siti|
|000005d0| 02 4a 50 61 72 74 53 49 | 54 21 00 00 00 00 00 00 |.JPartSI|T!......|
|000005e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000005f0| 00 00 b1 b0 40 8e 00 00 | 00 00 00 00 01 9a 00 00 |....@...|........|
|00000600| 00 00 29 bc 7f 92 00 00 | 00 00 20 52 65 3a 20 46 |..).....|.. Re: F|
|00000610| 6f 6c 64 65 72 20 48 69 | 65 72 61 72 63 68 79 20 |older Hi|erarchy |
|00000620| 44 75 70 6c 69 63 61 74 | 69 6f 6e 0d 00 00 00 00 |Duplicat|ion.....|
|00000630| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000640| 00 00 00 00 00 00 00 00 | 00 04 36 35 37 a4 00 00 |........|..657...|
|00000650| 00 00 00 00 00 00 00 00 | 00 01 be ab 00 00 05 f2 |........|........|
|00000660| 00 00 02 90 02 07 31 32 | 2f 35 2f 39 38 34 30 30 |......12|/5/98400|
|00000670| 30 32 31 3a 30 31 3a 35 | 36 20 31 39 39 38 00 00 |021:01:5|6 1998..|
|00000680| 00 00 00 48 00 0a 47 65 | 6e 65 76 61 00 00 00 00 |...H..Ge|neva....|
|00000690| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000006a0| 00 00 00 00 00 00 00 02 | 00 02 00 b0 00 19 02 4a |........|.......J|
|000006b0| 02 8f 00 b0 00 19 02 4a | 02 8f b1 ae b0 06 00 00 |.......J|........|
|000006c0| 04 9a 00 00 04 9a 00 00 | 02 28 01 00 00 00 00 04 |........|.(......|
|000006d0| 00 01 00 01 00 00 01 00 | 00 00 01 54 00 00 00 54 |........|...T...T|
|000006e0| 00 00 00 46 00 ce 0d f8 | 25 76 00 00 00 1c 00 46 |...F....|%v.....F|
|000006f0| 00 01 4d 50 53 52 00 00 | 00 12 4d 57 42 42 00 00 |..MPSR..|..MWBB..|
|00000700| 00 1e 03 ed ff ff 00 00 | 00 00 00 00 00 00 03 f0 |........|........|
|00000710| ff ff 00 00 00 4c 00 00 | 00 00 00 00 00 00 00 00 |.....L..|........|
|00000720| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000730| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000740| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000750| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000760| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000770| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
+--------+-------------------------+-------------------------+--------+--------+